/*
ID:luongho3
LANG:JAVA
TASK:bigbrn
 */
import java.io.File;
import java.io.PrintStream;
import java.util.Scanner;


public class bigbrn {

	int N, T;
	int[][] m, dp, co;

	public static void main(String[] args) throws Exception {
		bigbrn prob = new bigbrn();
		prob.read();
		prob.solve();
	}
	
	public void read() throws Exception {
		Scanner scanner = new Scanner(new File("bigbrn.in"));
		N =  scanner.nextInt();
		T = scanner.nextInt();
		m = new int[N+1][N+1];
		dp = new int[N+1][N+1];
		co = new int[N+1][N+1];
		for (int i=1;i<=T;++i) {
			int r, c;
			r = scanner.nextInt();
			c = scanner.nextInt();
			m[r][c] = 2;
		}
	}
	
	public void solve() throws Exception {
		PrintStream ps = new PrintStream(new File("bigbrn.out"));
		System.setOut(ps);
		
		// init
		for (int i=1;i<=N;++i) {
			for (int j=1;j<=N;++j) {
				co[i][j] = co[i-1][j] + co[i][j-1] - co[i-1][j-1];
				if (m[i][j] != 2) {
					co[i][j]++;
				}
			}
		}
		
		int biggest = 1;
		
		for (int i=1;i<=N;++i) {
			if (m[N][i] != 2) 
				dp[N][i] = 1;
		}
		
		for (int i=1;i<N;++i) {
			if (m[i][N] != 2)
				dp[i][N] = 1;
		}
		
		// dynamic programming
		for (int i=N-1;i>=1;--i) {
			for (int j=N-1;j>=1;--j) {
				if (m[i][j] == 2) {
					dp[i][j] = 0;
				}
				else {
					dp[i][j] = Math.min(dp[i+1][j], Math.min(dp[i][j+1], dp[i+1][j+1])) + 1;	
				}
				if (dp[i][j] > biggest) {
					biggest = dp[i][j];
				}
			}
		}
		
		System.out.println(biggest);
		ps.close();
	}

}
